import com.sun.org.apache.xpath.internal.operations.Bool;

import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }





public class Demo6 {



    /*List<Integer> path;
    List<List<Integer>> ret;
    boolean[] check;
    public List<List<Integer>> permuteUnique(int[] nums) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        check = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,0);
        return ret;

    }

    private void dfs(int[] nums, int pos) {
        if (pos == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i=0;i<nums.length; i++){
            if (check[i] != true && (i==0||nums[i] != nums[i-1] || check[i-1]==false)){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums,pos+1);
                path.remove(path.size()-1);
                check[i]=false;
            }


        }


    }
*/



/*    int path;
    int sum;
    public int subsetXORSum(int[] nums) {

        dfs(nums,0);
        return sum;

    }

    private void dfs(int[] nums, int pos) {
        sum+=path;
        for(int i=pos;i<nums.length;i++){
            path^=nums[i];
            dfs(nums,i+1);
            path^=nums[i];
        }

    }*/







   /* int sum = 0;
    int tmp = 0;
    List<Integer> path;
    public int subsetXORSum(int[] nums) {
        path = new ArrayList<>();
        dfs(nums,0);
        return sum;
    }

    private void dfs(int[] nums, int pos) {
        //计算当前子集异或之和
        for(int i = 0;i<path.size();i++){
             tmp ^= path.get(i);
        }
        sum+=tmp;
        tmp=0;

        for(int i = pos;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size() - 1);
        }



    }*/





/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int left = 0;
        int right = 0;
        String ret = "";
        int count = 0;
        while (right < str.length()) {
            if (right < str.length() && str.charAt(right) >= '0' && str.charAt(right) <= '9') {
                right++;

            } else {
                right++;
                left = right;
            }


            int tmp = right - left;
            if (tmp > count) {
                count = tmp;
                ret = "";
                for (int i = left; i < right; i++) {
                    ret += str.charAt(i);
                }
            }



        }
        System.out.println(ret);
    }*/

   /* List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret=new ArrayList<>();
        path = new ArrayList<>();

        dfs(nums,0);
        return ret;
    }

    private void dfs(int[] nums, int pos) {
        ret.add(new ArrayList<>(path));

        for(int i=pos;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size() - 1); //恢复现场
        }

    }


*/




   /* private void dfs(int[] nums, int pos) {

        if (pos==nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        //选
        path.add(nums[pos]);
        dfs(nums,pos + 1);
        //恢复现场
        path.remove(path.size()-1);
        //不选
        dfs(nums, pos + 1);

    }*/





  /*  public List<List<Integer>> ret;
    public List<Integer> path;
    public boolean[] check;

    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret;

    }

    private void dfs(int[] nums) {
        if (check.length == nums.length){
            ret.add(path);
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if (check[i] == false){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                //剪枝
                check[i] = false;
                path.remove(nums.length - 1);
            }
        }
    }*/








    /*List<String> ret;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        dfs(root,new StringBuilder());
        return ret;

    }

    private void dfs(TreeNode root, StringBuilder _path) {
        StringBuilder path = new StringBuilder(_path);
        path.append(Integer.toString(root.val));
        if (root.left == null && root.right==null){
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if (root.left !=null) {
            dfs(root.left,path);
        }
        //恢复现场
        if (root.right != null){
            dfs(root.right,path);
        }


    }
*/








    /*
    int ret = 0;
    int tmp = 0;
    public int kthSmallest(TreeNode root, int k) {
        qTree(root,k);
        return ret;
    }


    private void qTree(TreeNode root,int k) {

        if (root == null || tmp>=k){
            return;
        }

        qTree(root.left,k);
        ret = root.val;
        tmp++;
        if (tmp>=k){
            return;
        }
        qTree(root.right,k);

    }

*/

    /*
    Long tmp = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root==null){
            return true;
        }

        boolean isLeft = isValidBST(root.left);
        if (isLeft==false){
            return false;
        }
        if (tmp>=root.val){
            return false;
        }else{
            tmp=(long)root.val;
        }

        boolean isRight = isValidBST(root.right);

        return isLeft&&isRight;

    }
*/

    /*
    public TreeNode pruneTree(TreeNode root) {
        if (root == null){
            return null;
        }

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left==null && root.right==null && root.val==0){
            return null;
        }
        return root;


    }
*/

}






